#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;
ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pre = newHead;
    ListNode* L1 = list1;
    ListNode* L2 = list2;
    while (L1 != NULL && L2 != NULL)
    {
        pre->next = L1->val < L2->val ? L1 : L2;
        if (L1->val < L2->val)
        {
            pre = L1;
            L1 = L1->next;
        }
        else
        {
            pre = L2;
            L2 = L2->next;
        }
    }
    if (L1 != NULL)
        pre->next = L1;
    else
        pre->next = L2;
    return newHead->next;
}
void test()
{
    ListNode* list1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l1a = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l1b = (ListNode*)malloc(sizeof(ListNode));
    ListNode* list2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l2a = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l2b = (ListNode*)malloc(sizeof(ListNode));
    list1->val = 1;
    l1a->val = 2;
    l1b->val = 4;
    list2->val = 1;
    l2a->val = 3;
    l2b->val = 4;
    list1->next = l1a;
    l1a->next = l1b;
    l1b->next = NULL;
    list2->next = l2a;
    l2a->next = l2b;
    l2b->next = NULL;
    ListNode* ret = mergeTwoLists(list1, list2);
    while (ret != NULL)
    {
        printf("%d ", ret->val);
        ret = ret->next;
    }
    printf("\n");
}
int main()
{
    test();
	return 0;
}